package com.zp.self.module.level_4_算法练习.算法.二分查找;

/**
 * @author By ZengPeng
 */
public class 力扣_367_有效的完全平方数 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_367_有效的完全平方数().isPerfectSquare(16));
        System.out.println(new 力扣_367_有效的完全平方数().isPerfectSquare(14));
        System.out.println(new 力扣_367_有效的完全平方数().isPerfectSquare(1));
        System.out.println(new 力扣_367_有效的完全平方数().isPerfectSquare(2));
        System.out.println(new 力扣_367_有效的完全平方数().isPerfectSquare(3));
        System.out.println(new 力扣_367_有效的完全平方数().isPerfectSquare(2147395600));
        System.out.println(new 力扣_367_有效的完全平方数().isPerfectSquare(Integer.MAX_VALUE));
        System.out.println(new 力扣_367_有效的完全平方数().isPerfectSquare(5));
    }

    /**
     * 题目：给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
     * 进阶：不要 使用任何内置的库函数，如  sqrt 。
     *
     * 分析：
     *      1.left =1,right =num/2;  使用二分法  跳过不必要   num / i = i  && num%i =0
     *
     * 边界值 & 注意点：
     *      1.
     **/
    public boolean isPerfectSquare(int num) {
        //思考：使用二分法  跳过不必要的值
        int left =1,right =num/2;
        while (left<=right){
            int mid = left +((right-left)>>1);
            int shang = num / mid;
            if(shang<mid){
                right= mid-1;
            }else if(shang>mid){
                left=mid+1;
            }else {
                if(num%mid ==0)return true;
                else  right= mid-1;
            }
        }
        return num==1;
    }
}
